/*
 * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
 * Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Class.java to edit this template
 */
package com.sx.sx1.lintcode.day717;

/**
 *
 * @author Administrator
 */
import java.util.*;

public class LC1339 {

    static class Solution {

        /**
         * @param nums:
         * @return: Find the maxmum range value. A range value is defined as the
         * minimum value times the sum of all values in a range.
         */
        public int maxRange(int[] nums) {
            // write your code here
            int n = nums.length;
            int[] sum = new int[n];
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                cnt += nums[i];
                sum[i] = cnt;
            }

            //arr[i][0]:  i左边第一个比i位置小的位置
            //arr[i][1]:  i右边第一个比i位置小的位置
            int[][] help = new int[n][2];
            Stack<List<Integer>> stk = new Stack<>();
            for (int i = 0; i < n; i++) {
                while (!stk.isEmpty() && nums[stk.peek().get(stk.peek().size() - 1)] > nums[i]) {
                    List<Integer> idxs = stk.pop();
                    int leftless = stk.isEmpty() ? -1 : stk.peek().get(stk.peek().size() - 1);

                    for (int idx : idxs) {
                        help[idx][0] = leftless;
                        help[idx][1] = i;
                    }
                }

                if (!stk.isEmpty() && nums[stk.peek().get(0)] == nums[i]) {
                    stk.peek().add(i);
                } else {
                    List<Integer> ll = new ArrayList<>();
                    ll.add(i);
                    stk.add(ll);
                }
            }

            while (!stk.isEmpty()) {
                List<Integer> idxs = stk.pop();
                int leftless = stk.isEmpty() ? -1 : stk.peek().get(stk.peek().size() - 1);
                for (int idx : idxs) {
                    help[idx][0] = leftless;
                    help[idx][1] = -1;
                }
            }

            int ans = nums[0];
            for (int i = 0; i < n; i++) {
                int rightsum = 0;
                if (help[i][1] == -1) { //i右边没有i位置更小的数了，那么i就是最小的
                    rightsum = sum[n - 1];
                } else { //i右边第一个比i小的数是help[i][1], 那么help[i][1]-1到i最小的位置是i位置
                    rightsum = sum[help[i][1] - 1];
                }

                int leftsum = 0;
                if (help[i][0] == -1) { //i左边没有比i位置更小的数了
                    leftsum = 0;
                } else { //i左边没有比i位置更小的数是help[i][0],那么help[i][0]+1  到i位置最小的数是i位置
                    leftsum = sum[help[i][0]];
                }

                int cursum = (rightsum - leftsum) * nums[i];
                if (ans < cursum) {
                    ans = cursum;
                }
                //System.out.println(help[i][0] + " " + help[i][1]);
            }

            return ans;
        }
    }

    public static void main(String[] args) {
        int[] p1 = {6, 2, 1};
        Solution obj = new Solution();
        System.out.println(obj.maxRange(p1));
    }

    static class Solution1 {

        /**
         * @param nums:
         * @return: Find the maxmum range value. A range value is defined as the
         * minimum value times the sum of all values in a range.
         */
        public int maxRange(int[] nums) {
            int n = nums.length;
            int[] sum = new int[n];
            int[] sum1 = new int[n + 1];
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                cnt += nums[i];
                sum[i] = cnt;

            }

            int[][] arr = new int[n][2];
            Stack<List<Integer>> s = new Stack<>();
            for (int i = 0; i < n; i++) {
                while (!s.isEmpty() && nums[s.peek().get(0)] > nums[i]) {
                    List<Integer> indexes = s.pop();
                    for (Integer index : indexes) {
                        int left = s.isEmpty() ? -1 : s.peek().get(s.peek().size() - 1);
                        arr[index][0] = left;
                        arr[index][1] = i;
                    }
                }
                if (!s.isEmpty() && nums[s.peek().get(0)] == nums[i]) {
                    s.peek().add(i);
                } else {
                    List<Integer> t = new ArrayList<>();
                    t.add(i);
                    s.add(t);
                }
            }

            while (!s.isEmpty()) {
                List<Integer> indexes = s.pop();
                for (Integer index : indexes) {
                    int left = s.isEmpty() ? -1 : s.peek().get(s.peek().size() - 1);
                    arr[index][0] = left;
                    arr[index][1] = -1;
                }
            }
            int max = 0;
            for (int i = 0; i < n; i++) {
                int rightSum = arr[i][1] == -1 ? sum[n - 1] : sum[arr[i][1] - 1];
                int curSum = rightSum - (arr[i][0] == -1 ? 0 : sum[arr[i][0]]);
                max = Math.max(max, curSum * nums[i]);
            }
            return max;
        }
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
1339 · 最大区间
算法
困难
通过率
53%

题目
题解11
笔记
讨论2
排名
记录
描述
给定一个非负数的整数数组，需要选出一个区间, 使得该区间是所有区间中值最大的一个，我们定义一个区间的值为：区间中的最小数 * 区间所有数的和。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


数据范围：1 ≤ len(nums) ≤ 1e6； 0 ≤ nums[n] ≤ 100;

样例
样例 1:

输入：[6, 2, 1]
输出：36
解释：所有区间及其对应的值为：

[6] = 6 * 6 = 36;

[2] = 2 * 2 = 4;

[1] = 1 * 1 = 1;

[6,2] = 2 * 8 = 16;

[2,1] = 1 * 3 = 3;

[6, 2, 1] = 1 * 9 = 9;

因此，最大的值为36。
挑战
最直观的算法复杂度是 
O
(
n
2
)
O(n 
2
 ) ，请在此基础上优化你的算法。

标签
推荐课程

系统设计 System Design 2024版
数据库、API、GFS、视频流等16大系统设计详解，实战练习拿下面试/晋升“拦路虎”
已开启智能提示
发起考试
45 分 00 秒
123456789
public class Solution {
    /**
     * @param nums: 
     * @return: Find the maxmum range value. A range value is defined as the minimum value times the sum of all values in a range.
 */
 /*
public int maxRange(int[] nums) {
        // write your code here
    }
}
控制台
历史提交

 */
